import java.awt.List;
import java.util.ArrayList;

/*
 * @lc app=leetcode.cn id=77 lang=java
 *
 * [77] 组合
 *
 * https://leetcode-cn.com/problems/combinations/description/
 *
 * algorithms
 * Medium (71.76%)
 * Likes:    190
 * Dislikes: 0
 * Total Accepted:    28.2K
 * Total Submissions: 39.2K
 * Testcase Example:  '4\n2'
 *
 * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 *
 * 示例:
 *
 * 输入: n = 4, k = 2
 * 输出:
 * [
 * ⁠ [2,4],
 * ⁠ [3,4],
 * ⁠ [2,3],
 * ⁠ [1,2],
 * ⁠ [1,3],
 * ⁠ [1,4],
 * ]
 *
 */

// @lc code=start
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        dfs(k, res, list, 1, n);
        return res;
    }

    void dfs(int n, List<List<Integer>> res, List<Integer> list, int start, int end) {
        if(n==0) {
            res.add( new ArrayList(list));
            return;
        }
        for(int i=start; i <= end; i++) {
            list.add(i);
            dfs(n-1, res, list, i+1, end);
            list.remove(list.size()-1);
        }
    }
}
// @lc code=end

